|
In mathematics, the sieve of Eratosthenes (, ''kóskinon Eratosthénous''), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.〔Horsley, Rev. Samuel, F. R. S., "' or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," (''Philosophical Transactions'' (1683–1775), Vol. 62. (1772), pp. 327–347 ).〕 The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.〔 This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.〔 The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes. It is named after Eratosthenes of Cyrene, a Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the ''Introduction to Arithmetic'' by Nicomachus.〔Nicomachus, ''Introduction to Arithmetic'', I, 13. ()〕 The sieve may be used to find primes in arithmetic progressions.〔J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", (Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104 ).〕 ==Overview== A prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself. To find all the prime numbers less than or equal to a given integer ''n'' by Eratosthenes' method: # Create a list of consecutive integers from 2 through ''n'': (2, 3, 4, ..., ''n''). # Initially, let ''p'' equal 2, the smallest prime number. # Starting from 2''p'', enumerate the multiples of ''p'' by counting to ''n'' in increments of ''p'', and mark them in the list (these will be 2''p'', 3''p'', 4''p'', ... ; the ''p'' itself should not be marked). # Find the first number greater than ''p'' in the list that is not marked. If there was no such number, stop. Otherwise, let ''p'' now equal this new number (which is the next prime), and repeat from step 3. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below ''n''. The main idea here is that every value for ''p'' is prime, because we have already marked all the multiples of the numbers less than ''p''. Note that some of the numbers being marked may have already been marked earlier (e.g., 15 will be marked both for 3 and 5). As a refinement, it is sufficient to mark the numbers in step 3 starting from ''p''2, as all the smaller multiples of ''p'' will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when ''p''2 is greater than ''n''.〔 Another refinement is to initially list odd numbers only, (3, 5, ..., ''n''), and count in increments of 2''p'' in step 3, thus marking only odd multiples of ''p''. This actually appears in the original algorithm.〔 This can be generalized with wheel factorization, forming the initial list only from numbers coprime with the first few primes and not just from odds (i.e., numbers coprime with ''2''), and counting in the correspondingly adjusted increments so that only such multiples of ''p'' are generated that are coprime with those small primes, in the first place. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sieve of Eratosthenes」の詳細全文を読む スポンサード リンク
|